package chapter07;


import chapter02.MyUtil;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class game {
    static int[] x; // 当前位置安排
    static int n; // 角色
    static int[] max_atk; // 当前最大攻击力
    static int now_atk; // 当前攻击力
    static int bestf; // 当前最优值
    static int[][] M; // 初始位置数组

    //判断位置是否可行
    public static boolean position(int k){
        for (int i = 0; i < k; i++) {
            if(x[k]==x[i]){
                return false;
            }
        }
        return true;
    }

    public static void backtrack(int i) {
        if (i > n) {
            int t = 0;
            for (int j = 1; j <= n; j++)
                t += M[x[j]][j];
            if (t > bestf) {
                bestf = t;
                for (int j = 1; j <= n; j++)
                    max_atk[j] = x[j];
            }
        } else {
            for (int j = i; j <= n; j++) {
                MyUtil.swap(x, i, j);
                if(position(i)){
                    backtrack(i + 1);
                }
                MyUtil.swap(x, i, j);
            }
        }
    }

    public static void main(String[] args) {
        // 输入n个兵种
        FileInputStream fileInputStream = null;
        try {
            fileInputStream = new FileInputStream("src\\data.txt");
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        Scanner in =new Scanner(fileInputStream);
        n = in.nextInt();
        M = new int[n + 1][n + 1];
        x = new int[n + 1];
        max_atk = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                M[i][j] = in.nextInt();
                // System.out.println(M[i][j] + " ");
            }
        }
        for (int i = 1; i <= n; i++) {
            x[i] = i;
        }
        bestf = 0;
        //回溯找到最优值
        backtrack(1);
        System.out.print("最大战力输出：");
        System.out.println(bestf);
        System.out.println("排兵阵法：");
        for (int i = 1; i <= n; i++) {
            System.out.print( max_atk[i] + " ");
        }
        System.out.println();
    }
}


